package list;

import java.util.ArrayList;
import java.util.Stack;
//给定一个序列，然后输入一个出栈顺序，判断是否是该序列的出栈序列
public class StackPopAndPush {

	//pushA表示序列，PopA表示出栈序列
	//其实应该用数组表示序列
	public static boolean isPopOrder(ArrayList<Integer> pushA, ArrayList<Integer> popA) {
		//新建一个栈
		Stack<Integer> stack = new Stack<Integer>();
		if (pushA.size() == 0 && popA.size() == 0)
			return true;
		for (int i = 0, j = 0; i < pushA.size(); i++) {
			stack.push(pushA.get(i));
			//peek是找到栈顶的元素而不弹出
			//以1.2.3.4.5为例，若popA是4.5.3.2.1
			//由于popA.get(0)为4，那么知道将4加入之后才执行循环
			//此时将栈中的4弹出，但是此时栈顶不为5，重新执行外界的循环，加入5.
			while ((!stack.empty()) && j<popA.size()&&(stack.peek() == popA.get(j))) {
				stack.pop();
				j++;
			}
		}
		return stack.empty() == true;
	}

	public static boolean isPopOrder(int[] pushA, int[] popA) {
		//新建一个栈
		Stack<Integer> stack = new Stack<Integer>();
		if (pushA.length == 0 && popA.length == 0)
			return true;
		for (int i = 0, j = 0; j< popA.length;) {
			//peek是找到栈顶的元素而不弹出
			//以1.2.3.4.5为例，若popA是4.5.3.2.1
			//由于popA.get(0)为4，那么知道将4加入之后才执行循环
			//此时将栈中的4弹出，但是此时栈顶不为5，重新执行外界的循环，加入5.
			if ((!stack.empty()) && (stack.peek() == popA[j])) {
				stack.pop();
				j++;
			}else if(i<pushA.length){
			     stack.push(pushA[i++]);
			}else{
				//如果把pushA的全部数据都添加完之后仍没有退出循环，则要么就是不是popOrder
				//要么就是除了弹出序列之外还有其他的数据，上面的函数没有考虑当两个序列不一样长的情况
				return false;
			}
		}
		return true;
	}
	public static void main(String[] args) {

		int[] push={1,2,3,4,5};
		int[] pop={2,4,3,5,1};
		System.out.println(isPopOrder(push, pop));
	}

}
